package class05;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Code04_IsBST {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}


	//方法一：中序遍历 + 辅助结构List  ----- 最直观方法 --- 同随想录第一种
	public static boolean checkBST(Node root){
		if(root == null){
			return true;
		}
		List<Node> inOrderList = new ArrayList<>();

		inOrder(root, inOrderList);

		for (int i=0; i<inOrderList.size()-1; i++) {
			if ( inOrderList.get(i).value >= inOrderList.get(i+1).value ){
				return false;
			}
		}
		return true;
	}
	public static void inOrder(Node root, List inOrderList){ // 中序遍历并存放于List
		if (root == null){
			return;
		}
		inOrder(root.left, inOrderList);
		inOrderList.add(root);
		inOrder(root.right, inOrderList);
	}



	//方式二：递归 + 没有辅助结构  --- 对应随想录的第二种 -----
	public static long preValue = Long.MIN_VALUE; // 定义一个全局的的最小值。如果LeetCode测试数据包含Integer.MIN_VALUE，此处也可以改为Long.MIN_VALUE
	//todo： 在LeetCode中要尽量避免使用全局变量，更要避免使用static关键字

	public static boolean checkBST2(Node root) {
		if (root == null) { // 二叉搜索树可以为空
			return true;
		}

		boolean left = checkBST(root.left); // 判断 左

		if (root.value <= preValue) {  // 中序遍历，验证遍历的元素是不是从小到大
			return false;
		} else {
			preValue = root.value; // 如果不违规，将当前值设置为preValue
		}

		boolean right = checkBST(root.right); // 判断 右

		return left && right;
	}

	//方式二点五：（方式二的改进）递归 + 没有辅助结构 + 如果测试数据中有long的最小值，此时无法载初始化更小的最小值
	// --- 对应随想录的第二种的改进 -----

	static Node pre = null; // 用于记录前一个节点
	public static boolean checkBST2_1(Node root) {

		if (root == null) {
			return true;
		}

		boolean left = checkBST2_1(root.left); // 左

		if (pre != null && root.value >= pre.value) {
			return false;
		} else {
			pre = root; // 更新前一个节点
		}

		boolean right = checkBST2_1(root.right);

		return left && right;
	}



	// 方式三：中序遍历的迭代法 + MIN_VALUE
	static long preVal = Long.MIN_VALUE;  // ------ 预先设置最小值用于比较
	public static boolean checkBST3(Node root) {

		if (root == null) {
			return true;
		}

		Stack<Node> stack = new Stack<Node>();
		while (!stack.isEmpty() || root != null) {
			if (root != null) {
				stack.push(root);
				root = root.left;

			} else {
				root = stack.pop();

				if (root.value <= preVal) {
					return false;
				} else {
					preVal = root.value;
				}

				root = root.right; // 然后root移动到它的右节点去。 如果右树存在，则继续走if语句
			}
		}
		return true;
	}

	// 方式三点五：(方式三的改进) 中序遍历的迭代法 + pre节点
	static Node preNode = null;  // ------ 预先设置最小值用于比较
	public static boolean checkBST3_1(Node root) {

		if (root == null) {
			return true;
		}

		Stack<Node> stack = new Stack<Node>();
		while (!stack.isEmpty() || root != null) {
			if (root != null) {
				stack.push(root);
				root = root.left;

			} else {
				root = stack.pop();

				if (preNode != null && root.value <= preNode.value) {
					return false;
				} else {
					preNode = root; // 保存访问的前一个节点
				}

				root = root.right; // 然后root移动到它的右节点去。 如果右树存在，则继续走if语句
			}
		}
		return true;
	}






/*  没什么用的，重的
	public static boolean isBST(Node head) {
		if (head == null) {
			return true;
		}
		LinkedList<Node> inOrderList = new LinkedList<>();
		process(head, inOrderList);
		int pre = Integer.MIN_VALUE;
		for (Node cur : inOrderList) {
			if (pre >= cur.value) {
				return false;
			}
			pre = cur.value;
		}
		return true;
	}

	public static void process(Node node, LinkedList<Node> inOrderList) {
		if (node == null) {
			return;
		}
		process(node.left, inOrderList);
		inOrderList.add(node);
		process(node.right, inOrderList);
	}*/



	// --------------------------------
	// 方式四 二叉树递归套路
	public static class ReturnData {
		public boolean isBST;
		public int min;
		public int max;
		public ReturnData(boolean isBST, int min, int max) {
			isBST = this.isBST;
			min = this.min;
			max = this.max;
		}
	}


	public static ReturnData process(Node x){
		//base case
		if (x == null) {
			return null;
		}

		ReturnData leftData = process(x.left);
		ReturnData rightData = process(x.right);


		//预设值+排除

		int min = x.value;
		int max = x.value;
		if (leftData!=null) { // 说明左侧有子节点
			min = Math.min(min, leftData.min);
			max = Math.max(max, leftData.max);
		}
		if (rightData!=null) {
			min = Math.min(min, rightData.min);
			max = Math.max(max, rightData.max);
		}

/*方式一：
		boolean isBST = true;
		if ( leftData!=null && (!leftData.isBST || leftData.max>=x.value) ) {
			isBST = false;
		}
		if ( rightData!=null && ( !rightData.isBST || x.value>= rightData.min) ) {
			isBST = false;
		}*/

		//方式二
		boolean isBST = false;
		if (
				(leftData != null ? (leftData.isBST && leftData.max<x.value) : true )
				&&
				(rightData != null ? (rightData.isBST && rightData.min>x.value) : true)
		) {
			isBST = true;
		}



		return new ReturnData(isBST, min, max);

	}


}
